//
// Created by lanlu on 2025/8/12.
//

#include <vector>
#include <iostream>
using namespace std;

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        // 遍历数组 构建堆 大根堆/小根堆
        // 如果使用大根堆 想要得到递增的排序结果
        // 可以获取堆顶元素 删除堆顶元素 让剩余元素重新排列

        // 对于长度为n的数组 对应的完全二叉树
        // 构建堆的起始位置为 n/2-1  也就是非叶子节点 往前处理所有父节点
        // n=5 {0,1,2,3,4}  5/2-1=1
        for (int i = nums.size() / 2 - 1; i >= 0; i--)
        {
            // heapizy(nums, i, nums.size());
            heapizyByRec(nums, i, nums.size());
        }

        // 将堆顶元素和末尾元素交换 然后删除
        for (int i = nums.size() - 1; i > 0; i--)
        {
            // 交换首尾元素
            swap(nums[0], nums[i]);
            // 重新堆化 每交换一次堆中元素减少一个
            heapizy(nums, 0, i);
        }
        return nums;
    }

    // 构建大根堆
    // 参数为 数组 索引 堆大小
    // 数组就是要排成大根堆的所有元素序列
    // 索引就是要处理元素的索引位置  父节点
    // 堆大小就是最终得到的堆的大小
    void heapizy(vector<int> &nums, int k, int size)
    {
        // 通过索引获取当前元素 k看作父节点的索引
        int temp = nums[k];
        // 查找当前元素在堆中的位置
        // 索引为k的节点，左右孩子分别是索引 2k+1 和索引 2k+2
        for (int i = k * 2 + 1; i < size; i = i * 2 + 1)
        {
            // 先比较左右孩子 哪个值更大 让i 指向这个值
            // 如果左孩子的值 小于 右孩子的值 那么将i赋值为右孩子
            if (i + 1 < size && nums[i] < nums[i + 1]) i++;

            // 通过k 找到左孩子 2k+1=i  再通过i 找到2i+1
            // 如果子节点小于父节点 找到位置 结束
            if (nums[i] < temp) break;
            // 当构造大根堆时  如果子节点大于父节点 将子节点的值赋给父节点
            if (nums[i] > temp)
            {
                // 将子节点的值赋给父节点
                nums[k] = nums[i];
                // 更新当前位置
                k = i;
            }
        }
        // 循环结束后 k为当前节点的最终位置
        nums[k] = temp;
    }

    // 堆化的另一种写法
    void heapizyByRec(vector<int> &nums, int k, int size)
    {
        // 查找最大值索引
        int largest = k;
        // 左右孩子的索引
        int left = k * 2 + 1;
        int right = k * 2 + 2;
        if (left < size && nums[left] > nums[largest])
        {
            largest = left;
        }

        if (right < size && nums[right] > nums[largest])
        {
            largest = right;
        }

        if (largest != k)
        {
            swap(nums[k],  nums[largest]);
            // 递归处理子树
            heapizyByRec(nums, largest, size);
        }
    }

    void swap(int &a, int &b)
    {
        int temp = a;
        a = b;
        b = temp;
    }
};

int main()
{
    //                  0 1 2 3 4
    vector<int> nums = {4,6,8,5,9};
    vector<int> res = Solution().sortArray(nums);
    for (int i : res)
    {
        cout << i << " ";
    }
    cout << endl;
    return 0;
}
